//15.三数之和

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


class Solution1 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);
        //2.利用双指针解决问题
        //固定数
        for(int i = 0;i<nums.length;){
            if(nums[i] > 0){
                break;
            }
            int left = i+1;
            int right = nums.length-1;
            int target = -nums[i];
            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum < target){
                    left++;
                }else if(sum > target){
                    right--;
                }else{
                    //找到三数之和等于0的数
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //缩小范围继续查找
                    left++;
                    right--;
                    //去重 left right
                    while(left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while(left <right && nums[right] == nums[right+1]){
                        right--;
                    }
                }  
            }
             //去重 i
                i++;
                while(i < nums.length && nums[i] == nums[i-1]){
                    i++;
                }
        }
        return ret;
    }
}